package 二叉树相关问题.经典二叉树问题;


public class 从中序遍历和后序遍历构造二叉树 {

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
    }

    private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart>inEnd || postStart>postEnd)
            return null;
        int rootVal=postorder[postEnd];
        int index=0;
        for (int i = inStart; i<=inEnd ; i++) {
            if (inorder[i]==rootVal){
                index=i;
                break;
            }
        }
        TreeNode root=new TreeNode(rootVal);
        int leftLength=index-inStart;
        root.left=buildTree(inorder,inStart,index-1,postorder,postStart,postStart+leftLength-1);
        root.right=buildTree(inorder,index+1,inEnd,postorder,postStart+leftLength,postEnd-1);
        return root;
    }


}
